package com.test.daily.leetcode.y2022.m07.day0707.v02;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/12 下午 03:04
 * @version: 1.0
 */
public class Solution {
    public static int process(int[] arr, int left, int right) {
        int mid = left + ((right - left) >> 1);
        return process(arr, left, mid)
                + process(arr, mid + 1, right)
                + merge(arr, left, mid, right);
    }

    public static int merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int p1 = mid, p2 = right;
        int i = right - left;
        int ans = 0;
        while(p1 >= left && p2 >= mid + 1){
            ans += arr[p1] > arr[p2] ?  (p2 - mid) : 0;
            help[i--] = arr[p1] > arr[p2] ? arr[p1--]: arr[p2--];
        }
        while(p1 >= left){
            help[i--] = arr[p1--];
        }
        while(p2 >= mid+1){
            help[i--] = arr[p2--];
        }
        i = 0;
        for (; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        return ans;
    }
}
